package com.lik.javadeep.offer.test03;

/**
 * O(n)、O(1)
 * 绑定题目前提：所有数字都在 0～n-1 的范围内
 */
public class T3 {
    private static class Solution {
        // public int findRepeatNumber(int[] nums) {
        //     for (int i = 0; i < nums.length; i++) {
        //         int current=nums[i];
        //         int target;
        //
        //         while (current != i) {
        //             target = nums[current];
        //
        //             if (current == target) {
        //                 return current;
        //             }
        //             swap(nums, current, i);
        //             current = nums[i];
        //         }
        //     }
        //     return -1;
        // }
        public int findRepeatNumber(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                while (nums[i] != i) {
                    if (nums[i] == nums[nums[i]]) {
                        return nums[i];
                    }
                    swap(nums, nums[i], i);
                }
            }
            return -1;
        }


        private void swap(int[] nums, int i, int j) {
            int temp;
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] ints = {2, 3, 1, 0, 2, 5, 3};
        int repeatNumber = new Solution().findRepeatNumber(ints);
        System.out.println(repeatNumber);
    }
}
